package com.zhang.sort;

import java.util.Arrays;

/**
 *  选择排序
 *
 * @author Lelezhang
 * @create 2019-12-01 16:19
 */
public class SelectSort {
    public static void main(String[] args) {
        //选择排序实现,事件复杂度o(n^2),n是数组长度,两次for循环
        //创建数据
        int[] arr = {59, -8, 102, -5, 63};
        System.out.println("排序前:" + Arrays.toString(arr));
        //调用选择排序
        int[] result = selectSort(arr);
        //输出结果
        System.out.println("排序后:" + Arrays.toString(result));

        //测试10W数据时间
        int[] testArr = new int[100000];
        for (int i = 0; i < 100000; i++) {
            testArr[i] = (int) (Math.random() * 1000000);
        }

        //耗时约3s
        long start = System.currentTimeMillis() / 1000;
        selectSort(testArr);
        long end = System.currentTimeMillis() / 1000;
        System.out.println("10W数据选择排序优化后耗时:" + (end - start) + " s");
    }

    //选择排序,给出一个数组
    public static int[] selectSort(int[] arr) {
        //第1轮:找到从arr[0]到arr[n-1]中的最小值,与arr[0]交换位置;排出第1小的值
        //第2轮:找到从arr[1]到arr[n-1]中的最小值,与arr[1]交换位置;排出第2小的值
        //......
        //第n-1轮:找到从arr[n-2]到arr[n-1]中的最小值,与arr[n-2]交换位置;排出第n小的值

        //创建一个临时变量,用于交换
        int tempMin = arr[0];
        //定义最小索引
        int minIndex = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            //初始化最小索引,假定开始比较的第一个元素为最小的
            minIndex = i;
            tempMin = arr[i];
            //从第i个数到数组的最后一个数找最小的值
            for (int j = i + 1; j < arr.length ; j++) {
                if (tempMin > arr[j]) {
                    //把最小的那数的索引赋值给minIndex
                    minIndex = j;
                    //把最小数的值赋值给tempMin
                    tempMin = arr[j];
                }
            }
            //该轮比较结束,将最小值放置到开始比较的最小索引处
            if (minIndex != i) {//如果第一个开始比较的不是最小的
                arr[minIndex] = arr[i];//无法使用j,但j赋值给了minIndex,arr[minIndex]就是原来的最小值
                arr[i] = tempMin;//最小值赋值给第一个开始比较的值
            }
        }
        return arr;
    }

}
